为什么不推荐 ArrayDeque 代替 Stack
hi 这是 dhl 的第 43 篇文章
个人微信: hi-dhl
这篇文章源于对 stack-vs-deque 文章的思考，也是对我上一篇文章 算法动画图解 | 被 "废弃" 的 Java 栈，为什么还在用 内容的补充。
http://baddotrobot.com/blog/2013/01/10/stack-vs-deque
通过这篇文章你将学习到以下内容：
为什么不推荐使用 Java 栈 JDK 推荐使用 ArrayDeque代替Stack真的合理吗如何实现一个真正意义上的栈
在开始讨论之前，我们先来简单的回顾上一篇文章的内容。
为什么不推荐使用 Java 栈
栈是 后入先出（LIFO） 的数据结构，入栈通常使用 push 操作，往栈中插入数据到栈底，出栈使用 pop 操作，从栈顶删除数据。
栈是非常好的数据结构，但是 Java 栈的实现，存在以下问题，所以 JDK 不推荐使用 Java 栈。
性能低
性能低是因为 Stack 继承自 Vector， 而 Vector 在每个方法中都加了锁，如下所示：
......
public synchronized void trimToSize() { }
public synchronized void ensureCapacity(int minCapacity) { }
public synchronized void setSize(int newSize) { }
public synchronized int capacity() { }
public synchronized int size() { }
public synchronized boolean isEmpty() { }
......
由于需要兼容老的项目，很难在原有的基础上进行优化，因此 Vector 就被淘汰掉了，因此使用 ArrayList 和 CopyOnWriteArrayList 来代替，在线程安全的情况下可以使用 CopyOnWriteArrayList，否则非线程安全的情况下可以使用 ArrayList。
破坏了原有的数据结构
栈的定义是在一端进行 push 和 pop 操作，除此之外不应该包含其他 入栈和出栈 的方法，但是 Stack 继承自 Vector，使得 Stack 可以使用父类 Vector 公有的方法，如下所示。
val stack = Stack<Int>()
stack.push(6)
stack.add(1,10)
stack.removeAt(1)
stack.pop()
stack.addAll(arrayListOf())
正如你所见，除了调用 push() 和 pop() 方法之外，还可以调用 addXXX()、 removeXXX() 等等方法，但是这样会破坏栈原有的结构。所以对于栈的数据结构，不应该有可以在任何位置添加或者删除元素的能力。
JDK 推荐使用 ArrayDeque 代替 Stack
在 JDK 文档中，栈的相关操作应该由 Deque 接口来提供，推荐使用 Deque 的子类 ArrayDeque 代替 Stack。如下图标注部分所示。
使用 Deque 接口来实现栈的功能有以下好处：
速度比 Stack快
这个类作为栈使用时可能比 Stack 快，作为队列使用时可能比 LinkedList 快。因为原来的 Java 的 Stack 继承自 Vector，而 Vector 在每个方法中都加了锁，而 Deque 的子类 ArrayDeque 并没有锁的开销。
屏蔽掉无关的方法
原来的 Java 的 Stack，包含了在任何位置添加或者删除元素的方法，这些不是栈应该有的方法，所以需要屏蔽掉这些无关的方法。
声明为 Deque 接口可以解决这个问题，在接口中声明栈需要用到的方法，无需管子类是如何是实现的，对于上层使用者来说，只可以调用和栈相关的方法。
大神不推荐使用 ArrayDeque 代替 Stack
既然使用 Deque 接口来实现栈有这么多好处，那为什么大神不推荐使用 ArrayDeque 代替 Stack。http://baddotrobot.com/blog/2013/01/10/stack-vs-deque
因为接口 Deque 是双端队列的线性数据结构, 也就是说可以在两端进行插入和删除操作。而栈只能在一端做插入和删除操作。
栈的定义是在一端进行 push 和 pop 操作，除此之外不应该包含其他 入栈和出栈 的方法，但是基于 Deque 接口来实现栈，还可以在另外一端进行操作，如下所示。
val stack: Deque<Int> = ArrayDeque()
stack.push(1)
stack.poll() // 栈为空时会抛出异常
stack.peek() // 栈为空时返回 null
stack.offerLast(2)
stack.pollLast()
stack.peekLast()
如上所示，还可以调用 offerLast() 、 pollLast() 、 peekLast() 等等方法，往队列的另一端插入数据。
如果是在做算法题目无论使用 ArrayDeque 还是 Stack 都可以，因为关注点不一样，在做算法题的时候，关注点在解决问题的算法逻辑思路上。但是在大型的项目中不建议直接使用 Stack，也不推荐使用 ArrayDeque 代替 Stack。我们可以基于 ArrayDeque 封装一个真正的栈，只允许在一端做插入和删除操作，如下所示。
interface Stack<E> {
fun push(e: E)
fun pop(): E?
fun peek(): E?
fun size(): Int
fun empty(): Boolean
}
class ArrayStack<E> : Stack<E> {
private val deque = ArrayDeque<E>()
override fun push(e: E) = deque.push(e)
override fun pop(): E? = deque.poll()
override fun peek(): E? = deque.peek()
override fun size() = deque.size
override fun empty(): Boolean = deque.isEmpty()
}
推荐阅读：
感谢大家帮忙 在看、点赞、分享 给身边更多的朋友
代码不止，文章不停
欢迎点击下方卡片关注我，查看最新技术文章
公众号简介：
hi 大家好，我是 DHL，专注分享最新技术原创文章，涉及 Kotlin、Jetpack、算法动画、系统源码 等等。
感谢你看到这里
就现在
给正在努力中的自己
点个 在看 吧↓↓↓
最后推荐我一直在更新维护的项目和网站：
个人博客，将所有文章进行分类，欢迎前去查看
https://hi-dhl.com更多 Kotlin 、Jetpack 开源项目，欢迎前往 github 查看
https://github.com/hi-dhlLeetCode / 剑指 offer / 国内外大厂面试题 / 多线程 题解，语言 Java 和 kotlin，包含多种解法、解题思路、时间复杂度、空间复杂度分析
剑指 offer：https://offer.hi-dhl.com
LeetCode：https://leetcode.hi-dhl.com「为互联网人而设计，国内国外名站导航」涵括新闻、体育、生活、娱乐、设计、产品、运营、前端开发、Android 开发等等网址
https://site.51git.cn